/**
 * 
 */
package tree;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.charset.Charset;

/**
 * @author michaelyi
 *
 *Reference: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=usingTries
 */
public class TrieDictionary {

	final static String DICTIONARY_NAME = ".\\dictionary.txt";
	protected TrieNode root = null;

	/**
	 * 
	 */
	public TrieDictionary() {
		root = new TrieNode();
	}
	
	public void addWord(String word) {
		root.addWord(word);
	}
	
	public int countWords(String word) {
		int result = 0;
		if (word != null)
			result = root.countWords(word);
			
		return result;
	}
	
	public int countPrefixes(String word) {
		int result = 0;
		if (word != null)
			result = root.countPrefixes(word);
		
		return result;
	}
	
	public TrieNode getRoot() {
		return root;
	}
	
	public void printDictionary() {
		printDictionayHelper(root, new StringBuilder());
	}

	private void printDictionayHelper(TrieNode node, StringBuilder sb) {
		if (node.numberOfWord > 0)
			System.out.printf("%s\n", sb.toString());

		for (int i = 0; i < TrieNode.EN_LETTERS_NUMBER; ++i) {
			if (node.nodes[i] != null) {
				sb.append((char)('a'+ i));
				printDictionayHelper(node.nodes[i], sb);
				sb.deleteCharAt(sb.length() - 1);
			}
		}
	}
	
	/**
	 * @param args
	 */
	
	public static TrieDictionary buildDictionary(String fileName) {
		if (fileName == null || fileName.equals(""))
			return null;
		
		TrieDictionary dictionary = new TrieDictionary();
		
		try {
			FileInputStream fis = new FileInputStream(fileName);
			InputStreamReader isr = new InputStreamReader(fis, Charset.defaultCharset());
			BufferedReader br = new BufferedReader(isr);
			
			try {
				String line = null;
				while ((line = br.readLine()) != null) {
					dictionary.addWord(line);
				}
			}
			finally {
				br.close();
			}
		}
		catch (FileNotFoundException fnfe) {
			fnfe.printStackTrace();
		}
		catch (IOException ioe) {
			ioe.printStackTrace();
		}
		
		return dictionary;
	}
	
	public static void main(String[] args) {
		System.out.println("Trie Dictionary");
		TrieDictionary dictionary = TrieDictionary.buildDictionary(System.getProperty("user.dir") + DICTIONARY_NAME);
		String word = "sole";
		System.out.printf("%s is existed: %s", word, dictionary.countWords(word) > 0 ? "true" : "false");
		
		//dictionary.printDictionary();
	}

}

class TrieNode {
	
	final static int EN_LETTERS_NUMBER = 26;
	int numberOfWord = 0;
	int numberOfPrefix = 0;
	TrieNode[] nodes;

	
	TrieNode() {
		this.numberOfWord = 0;
		this.numberOfPrefix = 0;
		this.nodes =  new TrieNode[EN_LETTERS_NUMBER];
	} 
	
	public void addWord(String word) {
		if (word.equals("")) {
			this.numberOfWord++;
		}
		else {
			numberOfPrefix++;
			Character ch = word.charAt(0);
			int index = ch - 'a';
			if (nodes[index] == null) {
				nodes[index] = new TrieNode();
			}
			nodes[index].addWord(word.substring(1, word.length()));
		}
	}
	
	public int countWords(String word) {
		assert(word != null);
		
		if (word.length() == 0) {
			return numberOfWord;
		}
		else {
			Character ch = word.charAt(0);
			int index = ch - 'a';
			if (nodes[index] == null) {
				return 0;
			}
			else {
				return nodes[index].countWords(word.substring(1, word.length()));
			}
		}
	}
	
	int countPrefixes(String word) {
		assert(word != null);
		
		if (word.length() == 0) {
			return numberOfPrefix;
		}
		else {
			Character ch = word.charAt(0);
			int index = ch - 'a';
			if (nodes[index] == null) 
				return 0;
			else
				return nodes[index].countPrefixes(word.substring(1, word.length()));
		}
	}
	
	
}